package DataStructure.arrayAndList.list.listReverse;

import DataStructure.arrayAndList.list.Nodelj;
import Top100.Reversal;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/12/7
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 每N个数反转一次
 */

public class ListReversePartN implements Reversal {

    public Nodelj reverse(Nodelj head, int n) {
        if (head == null) {
            return head;
        }
        ListReverseTwoPosition reverseListTool = new ListReverseTwoPosition();
        int count = 1;
        Nodelj nodeBegin = head;
        Nodelj nodeEnd = head;
        Nodelj nodePre = new Nodelj();
        Nodelj headPre = new Nodelj();
        nodePre.next = head;
        headPre.next = head;
        while (nodeEnd != null) {
            if (count % n == 0) {
                // 因为reverse操作存在head变化的情况，所以需要
                Nodelj nodeEndNext = nodeEnd.next;
                nodePre.next = reverseListTool.reverse(nodePre.next, nodeEnd);
                nodePre = nodeBegin;
                nodeBegin = nodeEndNext;
                nodeEnd = nodeEndNext;
            } else {
                nodeEnd = nodeEnd.next;
            }
            count++;
        }
        return head;
    }

    public Nodelj reverse1(Nodelj head, int n) {
        if (head == null) {
            return head;
        }
        ListReverseTwoPosition reverseListTool = new ListReverseTwoPosition();
        Nodelj node = head;
        int count = 1;
        int index1 = 1;

        while (node != null) {
            node = node.next;
            count++;
            if (count % n == 0) {
                // 因为reverse操作存在head变化的情况，所以需要
                head = reverseListTool.reverse(head, index1, count);
                index1 = count + 1;
            }
        }
        if (index1 < count) {
            reverseListTool.reverse(head, index1, count);
        }
        return head;
    }
}
